package record.book.capter02.sort.v1;

import record.U;

/**
 * 希尔排序，基础是插入排序
 * 插入排序对大规模乱序数组排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。
 *尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。换
 * 句话说，一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组（见图 2.1.2）。
 * 在进行排序时，如果 h 很大，我们就能将元素移动到很远的地方，为实现更小的 h 有序创造方便。用
 * 这种方式，对于任意以 1 结尾的 h 序列，我们都能够将数组排序。这就是希尔排序。
 */
public class ShellSort {
    /**
     * 本人思路：首先设计间隔为h，例如h=3，那么以3为间隔将arr分成多个数组，如索引号分别是[0,3,6,9][1,4,7,10][2,5,8]
     * 将这三个索引的数组排序完成后，逐步减少h的值，此时是2，则需要使用插入排序的数组索引号是[0,2,4,6,8,10][1,3,5,7,9]
     * 然后将间隔为2的数组拍完序后，将h缩减为1，再使用插入排序的数组索引号是[0,1,2,3,4,5,6,7,8,9,10]，
     * 主要思想是插入排序逐步的移动元素效率太低，通过间隔的方式，扩大元素移动的范围，逐步的将无序数组转变成大致有序最终由于，
     * 主要是利用插入排序的特点，插入排序的特点是数组如果有序，则插入排序的元素交换次数就会比较少，效率就会很高
     * @param arr
     */
    public static void sort(int[] arr){
        int h = arr.length/3;
        while (h>0){
            for(int i=0;i<arr.length;i++){
                int j = i;
                while (j>=0 && (j+h)<arr.length && arr[j+h]<arr[j]){
                    U.swap(arr,j,j+h);
                    j-=h;
                }
            }
            h--;
        }
    }
}
